/*
Source : https://leetcode.com/problems/permutations/
Author : nflush@outlook.com
Date   : 2016-07-26
*/

/*
46. Permutations

    Total Accepted: 110393
    Total Submissions: 296653
    Difficulty: Medium

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]
*/
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ret;
        if (nums.size() == 0) return ret;
        ret.push_back(nums);
        int size = nums.size();

        for (int i = 0; i < size -1; i++){
            int jMax = ret.size();
            for (int j=0; j<jMax; j++){
                vector<int> v = ret[j];
                for (int k = i+1; k < size; k++){
                    int t = v[i];
                    v[i] = v[k];
                    v[k] = t;
                    ret.push_back(v);
                }
            }
        }
        return ret;
    }
};


